1. The Field of the Invention
The present invention relates to methods for managing a color look-up table which is shared by program applications in a computer system. More particularly, the present invention relates to a method of analyzing color values based on a quality metric which reflects human visual perception.
2. The Relevant Art
Computer operating systems are increasingly required to display vivid, color images for applications such as video creation and editing, image and graphics display and manipulation, and the presentation of "web pages", the documents obtained from servers on the World-Wide-Web. Examples of such operating systems include the X-Window System, the Macintosh operating system, and Microsoft Windows. Program applications which generate color images require the host computer graphics system to be capable of allocating a set of color values for displaying those images. Certain program applications, such as web browsers and drawing programs, generate images requiring particularly large sets of color values. However, many computer graphics systems provide only a limited number of color value choices in a memory space which must be shared by multiple program applications. Most window systems automatically allocate a core set of color values upon initialization of the window system. Additional sets of color values are then allocated by user program applications. It is the task of the window system to manage the color values available in the shared memory space to satisfy the requirements of each active program application.
Typical computer graphics systems include a display buffer for storing a picture definition to be displayed on a display device. The most common type of graphics display device is a raster scan display comprising a cathode ray tube (CRT) monitor. In raster scan graphics systems, a memory area called a frame buffer is used to store a set of color values for each screen point, or pixel, of the display. The range of color values for each pixel position depends on the capability of the raster system. Black and white systems require only one bit per pixel to control the intensity of screen positions. Additional bits per pixel are required when color and intensity variations can be displayed. A typical raster scan CRT monitor displays color pictures using a set of primary colors (e.g., red, green, and blue phosphors) each activated by a separate electron gun. A wide range of colors can be generated at a pixel by combining intensity varied emitted light from each of the primary colors. If a computer graphics system uses 8 bits to control the intensity of each primary color, there are a total of 2.sup.(8.times.3) possible color choices for display. However, the actual number of color choices available to a user is limited by the amount of storage provided in the frame buffer. Color information can be stored in a frame buffer either directly or indirectly using a color look-up table, also called a color map. In a color raster system using a color look-up table, frame buffer values are used as indices into one or more color look-up tables. Color look-up tables provide additional color choices to a user without requiring larger frame buffers.
The number of color choices available in a computer graphics system can be increased by using well known digital techniques for approximating halftones. Many such techniques include the use of pixel grid patterns to approximate halftones. Pixel grid patterns reduce the resolution of the display in favor of increasing the number of colors which can be displayed. Dithering and error diffusion are two additional common computer graphics techniques for approximating halftones. In dithering and error diffusion techniques, a reduced set of stored color values (a reduced color set) is used to generate a larger set of display color values. A critical step in digital halftoning techniques comprises determining an error value between a color value, to be displayed by digital half toning, and a color value in the reduced color set. Typically, the reduced color set values are arranged as points that comprise a cube. This arrangement simplifies mathematical operations required by the various digital halftoning techniques.
An example of such a color cube is shown in FIG. 1 at 100. The color cube 100 represents a red, green, blue ("RGB") color space which consists of three color components shown as axes: red, green, and blue. The color cube 100 includes uniformly spaced memory spaces, or slots, referenced by RGB coordinate values. The color cube 100 is a 6.times.6.times.6 color cube which is the largest color cube which can fit into a 256 element color look-up table. The coordinates for each color value of color cube 100 can be generated by dividing each color axis of a 256.times.256.times.256 color cube by 5.
Most dithering and error diffusion techniques include determining an error value, .DELTA., between an RGB color value in the reduced color set and a display (RGB) color value using the simple Euclidean distance relationship below. ##EQU1## where R.sub.1, G.sub.1, and B.sub.1, are color components of a first color value and R.sub.2, G.sub.2, and B.sub.2 are color components of a second color value. The error value is used to represent the difference between the first and second color values for purposes of human visual perception.
However, RGB color space is non-uniform. That is, a given distance between a first pair of color values in RGB color space can correlate to little perceptual difference to the human eye whereas the same distance between a second pair of color values can correlate to a great perceptual difference to the human eye. So, using the simple Euclidean formula in RGB color space to determine error values between color values does not provide an optimal quality metric for analyzing colors for purposes of human visual perception. Thus, the above described error value determination method, in the non-uniform RGB color space, for dithering or error diffusion of images results in poor quality image displays.
Therefore, a method of determining error values between colors is needed wherein the method provides optimal results for analyzing colors for purposes of human visual perception. Also, a method of managing a color look-up table based on an optimal color quality metric is needed in order to be able to display optimal full color images while allocating a minimum number of new color values in the color look-up table.